package leetcode.N1501_N1600;


import java.util.Arrays;
import java.util.Random;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/11/9 9:18 下午
 */
public class N1502 {

    public static void main(String[] args) {
        N1502 n = new N1502();
        int[] i = {-68,-96,-12,-40,16};
        n.canMakeArithmeticProgression(i);
        System.out.println(Arrays.toString(i));
    }

    public boolean canMakeArithmeticProgression(int[] arr) {
        sort(arr);
        int val = arr[1] - arr[0];
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i + 1] - arr[i] != val) {
                return false;
            }
        }
        return true;
    }

    public void sort(int[] arr) {
        qsort(0, arr.length - 1, arr);
    }
    private void qsort(int startIndex, int endIndex, int[] arr) {
        if (startIndex >= endIndex) {
            // 待排序数组中  只有一个元素 或者  没有元素时  意味着不需要排序了
            return;
        }
        // 1. 随机选取一个 基准点
        int pivotIndex = new Random().nextInt(endIndex - startIndex) + startIndex;
        int pivotVal = arr[pivotIndex];
        // 2.遍历数组 进行比较
        for (int i = startIndex; i <= endIndex; i++) {
            int currentVal = arr[i];
            if (currentVal <= pivotVal) {
                // 如果当前值小于基准值 则当前值应该放在基准值左边
                if (i > pivotIndex) {
                    // 在右边 则需要变换位置
                    int right = arr[++pivotIndex];
                    arr[pivotIndex - 1] = currentVal;
                    arr[i] = right;
                    arr[pivotIndex] = pivotVal;
                }
            } else {
                // 大于基准值 则应该放在基准值得右边
                if (i < pivotIndex) {
                    // 在左边 需要变换
                    arr[pivotIndex] = arr[i];
                    arr[i] = pivotVal;
                    pivotIndex = i;
                }
            }
        }
        qsort(startIndex, pivotIndex - 1, arr);
        qsort(pivotIndex + 1, endIndex, arr);
    }


}
